// https://leetcode.cn/problems/subarray-sum-equals-k/

// 题干：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
//      子数组是数组中元素的连续非空序列。

// 示例：输入：nums = [1,1,1], k = 2
//       输出：2

// 碎语：当固定一个数，另一个数到达某一位置和为k的时候，right不能停
//       因此使用双指针的算法是不太明智的
//       以i位置为结尾的所有子数组也能相当于考虑所有子数组
//       采用哈希表，第一个int表示前缀和，第二个int表示次数
// 我们是求[0,i-1]区间内，有多少个前缀和等于sum[i]-k
// 在计算i位置之前，哈希表里面只保存[0,i-1]位置的前缀和

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int subarraySum(vector<int>& nums, int k)
    {
        int sum = 0, ret = 0;
        unordered_map<int, int> hash;
        hash[0] = 1;


        for (const auto& num : nums){
            sum += num; // 求出sum[i]

            // 求出[0,i-1]区间内前缀和满足sum[i]-k的个数，并且考虑到sum[i]-k为0的情形
            if (hash.count(sum - k)) ret += hash[sum - k];
            hash[sum]++; // 事后记得将前缀和放到哈希表中
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {1,1,1};

    cout << sol.subarraySum(nums, 2) << endl;

    return 0;
}